package ArvoresBinarias;

public class ArvorePesquisaBinaria 
{
	Memoria m = null;
	final int NIL = Integer.MAX_VALUE;
	int root = NIL;
	public ArvorePesquisaBinaria(int n)
	{
		this.m = new Memoria(n);
		
	}
	public void insert(int key)
	{
		int z = this.m.allocate_object();
		this.m.key[z]= key;
		
		int y = this.NIL;
		int x = this.root;
		while(x != this.NIL)
		{
		y= x;
		 if(this.m.key[z]< this.m.key[x])
		 {
			 x = this.m.left[x];
		 }
		 else
		 {
			 x = this.m.right[x];
		 }	
		
	}
	this.m.p[z]= y;
	if(y == this.NIL )
	{
		this.root = z;
	}
	else if(this.m.key[z]< this.m.key[y])
	{
		this.m.left[y]= z;
		
	}
	else
	{
		this.m.right[y] = z;
	}
	}

	@Override public String toString()
	{
		String s = this.m.toString()
			+"root ->"	
			+(this.root == Integer.MAX_VALUE ? "nil": this.root);
			return s;
	}
}
